11367 - Full tank?/comparación/11367.3.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <iostream>
   5 #include <vector>
   6 #include <queue>
   7 //#include <cassert>
   8
   9 using namespace std;
  10
  11 const int MAXN = 1000, MAXC = 100;
  12
  13 struct edge{
  14   int i, g, w;
  15   edge(){}
  16   edge(int I, int G, int W) : i(I), g(G), w(W) {}
  17   bool operator < (const edge &that) const {
  18     return w > that.w;
  19   }
  20 };
  21
  22 int p[MAXN], d[MAXN][MAXC+1], n, visited, maxQSize;
  23 vector<edge> g[MAXN];
  24
  25
  26 int dijkstra(const int &start, const int &end, const int &c){
  27   for (int i=0; i<n; ++i)
  28     for (int j=0; j<=c; ++j)
  29       d[i][j] = INT_MAX;
  30
  31   priority_queue<edge> q;
  32   q.push(edge(start, 0, 0));
  33   d[start][0] = 0;
  34
  35   while (q.size()){
  36
  37     maxQSize = max(maxQSize, (int)q.size());
  38
  39     edge u = q.top();
  40     q.pop();
  41
  42     //printf("popped <%d, %d, %d>\n", u.i, u.g, u.w);
  43     if (u.i == end){
  44       return u.w;
  45     }
  46     if (d[u.i][u.g] < u.w) continue;
  47
  48     ++visited;
  49
  50     //I can buy another gallon and stay where I am
  51     if (u.g < c && u.w + p[u.i] < d[u.i][u.g+1]){
  52       d[u.i][u.g+1] = u.w + p[u.i];
  53       q.push(edge(u.i, u.g+1, u.w + p[u.i]));
  54     }
  55
  56     //Now try to reach each other node as long as I have enough gas
  57     vector<edge> &v = g[u.i];
  58     for (int j=0; j<v.size(); ++j){
  59       int distance = v[j].w;
  60       int neighbor = v[j].i;
  61       if (u.g >= distance){
  62         int new_gas = u.g - distance;
  63         if (u.w < d[neighbor][new_gas]){
  64           d[neighbor][new_gas] = u.w;
  65           q.push(edge(neighbor, new_gas, u.w));
  66         }
  67       }
  68     }
  69   }
  70   return INT_MAX;
  71
  72 }
  73
  74 int main(){
  75   int m;
  76   scanf("%d %d", &n, &m);
  77   for (int i=0; i<n; ++i){
  78     scanf("%d", &p[i]);
  79   }
  80
  81   while (m--){
  82     int u, v, d;
  83     scanf("%d %d %d", &u, &v, &d);
  84     g[u].push_back(edge(v, 0, d));
  85     g[v].push_back(edge(u, 0, d));
  86   }
  87
  88   int q;
  89   scanf("%d", &q);
  90   while (q--){
  91     int c, s, e;
  92     scanf("%d %d %d", &c, &s, &e);
  93     visited = 0;
  94     maxQSize = 0;
  95     int t = dijkstra(s, e, c);
  96     if (t < INT_MAX){
  97       printf("%d\n", t);
  98     }else{
  99       printf("impossible\n");
 100     }
 101     printf(" Visited %d states with maximum queue size of %d\n", visited, maxQSize);
 102   }
 103   return 0;
 104 }